import java.util.Arrays;
import java.util.Stack;

/**
* @description: 915. 分割数组
* @author hewei
* @date 2022/9/17 14:35
* @version 1.0
*/

public class PartitionDisjoint {

    public static void main(String[] args) {
        PartitionDisjoint partitionDisjoint = new PartitionDisjoint();
        int[] nums = {18,14,2,8,10,0,5,17,4,18,4,16,68,49,71,61,64,51,98,37,52,93,46,88,34,63,35,32,32,67,94,79,40,89,20,61,58,45,93,96,71,46,66,26,21,28,52,96,80,21};
        System.out.println(partitionDisjoint.partitionDisjoint(nums));
    }

    public int partitionDisjoint1(int[] nums) {
        Stack<Integer> stack = new Stack<>();
        int n = nums.length;
        int[] temp = new int[n];
        int[] min = new int[n];
        int a = -1;
        Arrays.fill(temp, -1);
        for (int i = 0; i < n; i++) {
            if (a == -1 || nums[a] > nums[n - 1 - i]) {
                a = n - 1 - i;
            }
            min[n - 1 - i] = a;
            while (!stack.isEmpty() && nums[stack.peek()] <= nums[i]) {
                Integer pop = stack.pop();
                temp[pop] = i;
            }
            stack.push(i);
        }
        int ans = -1;
        for (int i = 0; i < n; i++) {
            if (i == ans) return ans;
            int b = temp[i];
            ans = Math.max(ans, b);
            if (nums[min[b]] < nums[i]) ans = Math.max(ans, min[b]);
        }
        return -1;
    }

    public int partitionDisjoint2(int[] nums) {
        int n = nums.length;
        int[] leftMax = new int[n];
        int[] rightMin = new int[n];
        rightMin[n - 1] = Integer.MAX_VALUE;
        leftMax[0] = nums[0];
        for (int i = 1; i < n; i++) {
            leftMax[i] = Math.max(nums[i], leftMax[i - 1]);
        }
        for (int i = n - 2; i >= 0; i--) {
            rightMin[i] = Math.min(nums[i + 1], rightMin[i + 1]);
        }
        for (int i = 0; i < n; i++) {
            if (leftMax[i] <= rightMin[i]) return i + 1;
        }
        return -1;
    }

    public int partitionDisjoint(int[] nums) {
        int targetMax = nums[0];
        int max = nums[0];
        int ans = 0;
        for (int i = 0; i < nums.length; i++) {
            max = Math.max(max, nums[i]);
            if (nums[i] < targetMax) {
                targetMax = max;
                ans = i;
            }
        }
        return ans + 1;
    }
}